package formal.tree.ergodic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的后序遍历-要求非递归
 *
 * @author DengYuan2
 * @create 2021-01-20 22:04
 */
public class M_145 {
    public static void main(String[] args) {
//        Integer[] a = {1,null,2,3,null};
        Integer[] a = {1, 2, 3, 4, 5, 6, 7};
        TreeNode treeNode = TreeNode.generateTree(a);
        List<Integer> res = postorderTraversal2(treeNode);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i) + "  ");
        }
    }

    /**
     * 我的写法
     * 思路：前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> tmp = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            tmp.push(pop);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        while (!tmp.isEmpty()) {
            resList.add(tmp.pop().val);
        }
        return resList;
    }

    /**
     * 大神的写法-有点赖皮
     *
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal2(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            resList.add(pop.val);
            if (pop.left!=null){
                stack.push(pop.left);
            }
            if (pop.right!=null){
                stack.push(pop.right);
            }
        }
        Collections.reverse(resList);
        return resList;
    }
}
